package com.gofaraway.service.左神算法课;


import java.util.Random;

/**
 * 两个链表相加
 * 给定两个链表的头节点 head1 和head2
 * 认为从左到右是某个数字从低位到高位，返回相加之后的链表
 * 例子：    4 -> 3 -> 6    2 -> 5 -> 3
 * 返回      6 -> 8 -> 9
 * 解释      634 + 352 = 986
 */
public class Code07_AddTwoNumbers {


    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {

        int l1 = listLength(head1);
        int l2 = listLength(head2);

        //长链
        ListNode L = l1 <= l2 ? head2 : head1;
        //短链
        ListNode S = L == head1 ? head2 : head1;

        ListNode nodeL = L;
        ListNode nodeS = S;

        ListNode last = nodeL;

        int carry = 0;
        int curNum = 0;

        while (nodeS != null) {

            curNum = nodeL.value + nodeS.value + carry;
            nodeL.value = curNum % 10;

            carry = curNum / 10;

            last = nodeL;

            nodeS = nodeS.next;
            nodeL = nodeL.next;
        }


        while (nodeL != null) {
            curNum = nodeL.value + carry;
            nodeL.value = curNum % 10;

            carry = curNum / 10;
            last = nodeL;
            nodeL = nodeL.next;
        }

        if (carry != 0) {
            last.next = new ListNode(1);
        }
        return L;
    }

    /**
     * 求链表长度
     */
    public static int listLength(ListNode listNode) {

        int length = 0;
        while (listNode != null) {
            length++;
            listNode = listNode.next;
        }
        return length;
    }


    /**
     * 单向链表
     */
    static class ListNode {

        public int value;

        public ListNode next;


        public ListNode(int value) {
            this.value = value;
        }

        public ListNode() {
        }
    }




    //=============================================对数器


    /**
     * 测试不通过是有一个 末尾为0的 边界case 没有处理好
     */
    public static void main(String[] args) {
        int testTimes = 100;
        boolean success = true;
        for (int i = 0; i < testTimes; i++) {
            ListNode head1 = generateRandomList();
            ListNode head2 = generateRandomList();
            ListNode head1Copy = copyList(head1);
            ListNode head2Copy = copyList(head2);
            ListNode result = Code07_AddTwoNumbers.addTwoNumbers(head1, head2);
            ListNode expected = addTwoNumbersBruteForce(head1Copy, head2Copy);
            if (!isEqual(result, expected)) {
                success = false;
                System.out.println("Test failed!");
                printList(head1Copy);
                printList(head2Copy);
                printList(result);
                printList(expected);
                break;
            }
        }
        if (success) {
            System.out.println("All tests passed!");
        }
    }


    /**
     * 复制链表
     */
    public static ListNode copyList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode newHead = new ListNode();
        ListNode currentNew = newHead;
        ListNode currentOld = head;

        while (currentOld != null) {
            currentNew.next = new ListNode(currentOld.value);
            currentNew = currentNew.next;
            currentOld = currentOld.next;
        }

        return newHead.next;
    }

    /**
     * 暴力解法：将链表转换为数字，相加后再转换回链表
     */
    private static ListNode addTwoNumbersBruteForce(ListNode head1, ListNode head2) {
        int num1 = listToNumber(head1);
        int num2 = listToNumber(head2);
        int sum = num1 + num2;
        return numberToList(sum);
    }

    /**
     * 将链表转换为数字
     */
    private static int listToNumber(ListNode head) {
        int num = 0;
        int place = 1;
        while (head != null) {
            num += head.value * place;
            place *= 10;
            head = head.next;
        }
        return num;
    }

    /**
     * 将数字转换为链表
     */
    private static ListNode numberToList(int num) {
        if (num == 0) {
            return new Code07_AddTwoNumbers.ListNode(0);
        }
        ListNode dummy = new Code07_AddTwoNumbers.ListNode();
        ListNode current = dummy;
        while (num > 0) {
            current.next = new Code07_AddTwoNumbers.ListNode(num % 10);
            current = current.next;
            num /= 10;
        }
        return dummy.next;
    }

    /**
     * 生成随机链表
     */
    private static ListNode generateRandomList() {
        Random random = new Random();
        int length = random.nextInt(8) + 1; // 随机长度，最多9个节点
        ListNode dummy = new Code07_AddTwoNumbers.ListNode();
        ListNode current = dummy;
        for (int i = 0; i < length; i++) {
            current.next = new Code07_AddTwoNumbers.ListNode(random.nextInt(10)); // 节点值为0-9
            current = current.next;
        }
        return dummy.next;
    }

    /**
     * 比较两个链表是否相等
     */
    private static boolean isEqual(ListNode head1, ListNode head2) {
        while (head1 != null && head2 != null) {
            if (head1.value != head2.value) {
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return head1 == null && head2 == null;
    }

    /**
     * 打印链表
     */
    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }
}
